{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Beautiful Arrangement"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #array #dynamic-programming #backtracking #bitmask"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #数组 #动态规划 #回溯 #状态压缩"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countArrangement"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #优美的排列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>假设有从 1 到 n 的 n 个整数。用这些整数构造一个数组 <code>perm</code>（<strong>下标从 1 开始</strong>），只要满足下述条件 <strong>之一</strong> ，该数组就是一个 <strong>优美的排列</strong> ：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>perm[i]</code> 能够被 <code>i</code> 整除</li>\n",
    "\t<li><code>i</code> 能够被 <code>perm[i]</code> 整除</li>\n",
    "</ul>\n",
    "\n",
    "<p>给你一个整数 <code>n</code> ，返回可以构造的 <strong>优美排列 </strong>的 <strong>数量</strong> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 2\n",
    "<strong>输出：</strong>2\n",
    "<b>解释：</b>\n",
    "第 1 个优美的排列是 [1,2]：\n",
    "    - perm[1] = 1 能被 i = 1 整除\n",
    "    - perm[2] = 2 能被 i = 2 整除\n",
    "第 2 个优美的排列是 [2,1]:\n",
    "    - perm[1] = 2 能被 i = 1 整除\n",
    "    - i = 2 能被 perm[2] = 1 整除\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 1\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 15</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [beautiful-arrangement](https://leetcode.cn/problems/beautiful-arrangement/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [beautiful-arrangement](https://leetcode.cn/problems/beautiful-arrangement/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['2', '1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countArrangement(self, n: int) -> int:\n",
    "        res = [0,1,2,3,8,10,36,41,132,250,700,750,4010,4237,10680,24679]\n",
    "        return res[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    result = 0\n",
    "    def helper(self,temp:list,arrange:list,index:int):\n",
    "        if len(temp) == 0:\n",
    "            self.result += 1\n",
    "\n",
    "        for i in range(len(temp)):\n",
    "            if temp[i] % index == 0 or index % temp[i] == 0:\n",
    "                newarrage = arrange + [temp[i]]\n",
    "                newtemp = temp[:i] + temp[i+1:]\n",
    "                self.helper(newtemp,newarrage,index+1)\n",
    "\n",
    "    def countArrangement(self, n: int) -> int:\n",
    "        temp = [i for i in range(1,n+1)]\n",
    "\n",
    "        self.helper(temp,[],1)\n",
    "        return self.result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countArrangement(self, n: int) -> int:\n",
    "        def backtrack(start, X):\n",
    "            if start == 1:\n",
    "                return 1\n",
    "            count = 0\n",
    "            for i in range(1, n + 1):\n",
    "                if X[i] and (start % i == 0 or i % start == 0):\n",
    "                    X[i] = False\n",
    "                    count += backtrack(start - 1, X)\n",
    "                    X[i] = True\n",
    "            return count\n",
    "        return backtrack(n, [True]*(n+1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countArrangement(self, n: int) -> int:\n",
    "        #首先我们从题上进行一些分析\n",
    "        #要注意，下标从1开始，而不是0\n",
    "        #从1开始意味着第一位可以是任何数\n",
    "        #用递归的办法做的话\n",
    "        #这道题需要我们记录哪些数用了，哪些数没有用，仅此而已。\n",
    "        #从复杂度上分析，这道题n最大只有15而已，这个其实是一个复杂度极高的算法，n!\n",
    "        #0表示未使用，1表示已经使用\n",
    "        def dfs(mask):#返回一个数字，代表数目\n",
    "            #print(bin(mask))\n",
    "            k = bin(mask).count('1')\n",
    "            if (k == n):                          \n",
    "                return 1\n",
    "            k += 1\n",
    "            ans = 0\n",
    "            for i in range(n):\n",
    "                num = i + 1\n",
    "                if ( (mask>>i) & 1 == 0  and ( num%k == 0 or k%num == 0) ) :\n",
    "                    ans += dfs(mask | (1<<i))\n",
    "            \n",
    "            return ans\n",
    "\n",
    "        return sum( [ dfs(1<<i) for i in range(n)])\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countArrangement(self, n: int) -> int:\n",
    "        could=[[] for _ in range(n+1)]\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(1,n+1):\n",
    "                if i%j==0 or j%i==0:\n",
    "                    could[i].append(j)\n",
    "        sel=[0]*(n+1)\n",
    "        def dfs(num):\n",
    "            if num==n+1:\n",
    "                return 1\n",
    "            ans=0\n",
    "            for i in could[num]:\n",
    "                if sel[i]==0:\n",
    "                    sel[i]=num\n",
    "                    ans+=dfs(num+1)\n",
    "                    sel[i]=0\n",
    "            return ans\n",
    "        return dfs(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countArrangement(self, n: int) -> int:\n",
    "        f=[0]*(1<<n)\n",
    "        f[0]=1#一个数字都能单独放在第1位，成为一个完美排列\n",
    "        #若 mask中的第 i 位为 1（从 0开始编号），则数 i+1 已经被选取，否则就还未被选取\n",
    "        #f[mask] 表示状态为 mask 时的可行方案总数\n",
    "        #以 n=4,mask=(0110)2   n = 4为例，这代表数 2,3 都已经被选取，并以任意顺序放置在排列中前两个位置\n",
    "        for mask in range(1,1<<n):\n",
    "            #对于mask中1的个数 如果中1的个数为k表示 已经选择了k个数字  并且一定是选择在前k个连续位置\n",
    "            #因此如果mask中已经存在了k个1  说明前面k个位置已经被选择了  下面应该选择第k+1个位置\n",
    "            #所以这里求的1的个数其实对应的是下标位置数\n",
    "            num=bin(mask).count('1')#代表序列中1的个数k\n",
    "            for i in range(n):#遍历这一次的序列选择哪个数  这里的i对应的才是数值选择的数\n",
    "                if (mask & (1<<i)) and (num % (i+1)==0 or (i+1) % num ==0):\n",
    "                    #因此我们想要得到选择数字i对应的结果数  因此mask中的第(i+1)为应该是置为1的\n",
    "                    #mask第(i+1)为1的是从 mask第(i+1)为0的所有的状态求和而来的\n",
    "                    #i + 1就是当前组合的一个整数  (i+1)这个数字作为数列中的第(i+1)为是合适的 (1<<i)表示从右向左数的第(i+1)位是1\n",
    "                    f[mask]+=f[mask^(1<<i)]\n",
    "        return f[(1<<n)-1]\n",
    "\n",
    "\n",
    "    # def __init__(self):\n",
    "    #     self.res=0\n",
    "\n",
    "    # def countArrangement(self, n: int) -> int:\n",
    "    #     used=[False]*(n+1)\n",
    "    #     self.backtracking(used,0,n,1)\n",
    "    #     return self.res\n",
    "    \n",
    "    # def backtracking(self,used,count,n,startindex):\n",
    "    #     if count==n:\n",
    "    #         self.res+=1\n",
    "    #         return\n",
    "        \n",
    "    #     for i in range(1,n+1):\n",
    "    #         if used[i]==False and (i%startindex==0 or startindex%i==0):\n",
    "    #             used[i]=True\n",
    "    #             self.backtracking(used,count+1,n,startindex+1)\n",
    "    #             used[i]=False\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countArrangement(self, n: int) -> int:\n",
    "        num_of_state = 1 << n\n",
    "        dp = [0 for _ in range(num_of_state)]\n",
    "        dp[0] = 1\n",
    "\n",
    "        for state_msk in range(num_of_state):\n",
    "            idx = bin(state_msk).count('1')\n",
    "\n",
    "            for num in range(1, n+1):\n",
    "                if state_msk & (1 << (num - 1)) == 0:\n",
    "                    # num is not used in this state\n",
    "                    continue\n",
    "                if num % idx == 0 or idx % num == 0:\n",
    "                    dp[state_msk] += dp[state_msk ^ (1 << (num-1))]\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countArrangement(self, n: int) -> int:\n",
    "\n",
    "        totnum=1<<n\n",
    "\n",
    "        #dp[mask]: 表示状态为mask时候方案数目\n",
    "        dp = [0] * (1 << n)\n",
    "        dp[0]=1\n",
    "        for mask in range(1, totnum):  # 对 1 到 2**m-1 进行枚举 (从1开始是因为0已经没有选择迁移的方法)\n",
    "            c = bin(mask).count(\"1\")  # 计算当前mask状态有几位 1， 然后枚举本次是从哪一位迁移过来的, c-1代表了前面已经处理完毕了\n",
    "            for i in range(n):  # 判断 mask 的第 i 位是否为 1\n",
    "                if mask & (1 << i):\n",
    "                    if c%(i+1)==0 or (i+1)%c==0:\n",
    "                        # 枚举位置 i 的放置位置， g[c-1][i]根据需要变化\n",
    "                        # c-1表示前面c-1个第一维数组已经被匹配完成了，现在需要匹配第c个人， 位置在第i处\n",
    "                        dp[mask] = dp[mask]+ dp[mask ^ (1 << i)]\n",
    "\n",
    "        return dp[(1 << n) - 1]  # f[\"11111111\"]即为最后的结果\n",
    "\n",
    "    def countArrangement2(self, n: int) -> int:\n",
    "\n",
    "        dp=[0 for i in range(n+1)]\n",
    "        tot=0\n",
    "\n",
    "        def dfs(seat:int, num:int):\n",
    "            nonlocal tot\n",
    "            if seat==n:\n",
    "                tot+=1\n",
    "#                print(dp)\n",
    "                return\n",
    "\n",
    "            dp[num]=seat\n",
    "            for i in range(1,n+1):\n",
    "                if dp[i]==0:\n",
    "                    if i%(seat+1)==0 or (seat+1)%i==0:\n",
    "                        dfs(seat+1,i)\n",
    "            dp[num] = 0\n",
    "\n",
    "        for i in range(1,n+1):\n",
    "            dfs(1,i)\n",
    "\n",
    "        return tot\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countArrangement(self, n: int) -> int:\n",
    "\n",
    "        dp = [0] * (1 << n)  # dp初始化为0， dp[s] 表示状态为s时候前 i+1 个人的最小/大累计值 ， 最初始位为 0\n",
    "        dp[0]=1\n",
    "        for mask in range(1, 1 << n):  # 对 1 到 2**m-1 进行枚举 (从1开始是因为0已经没有选择迁移的方法)\n",
    "            c = bin(mask).count(\"1\")  # 计算当前mask状态有几位 1， 然后枚举本次是从哪一位迁移过来的, c-1代表了前面已经处理完毕了\n",
    "            for i in range(n):  # 判断 mask 的第 i 位是否为 1\n",
    "                if mask & (1 << i):\n",
    "                    # 前面已经放置了0..c-1的位置， 目前想要在 c 这个位置放置数字 i\n",
    "                    #  perm[i] 能够被 i+1 整除\n",
    "                    #  i+1 能够被 perm[i] 整除\n",
    "                    if (i+1)%c==0 or c%(i+1)==0:\n",
    "#                        print(\"S:\",mask,\"= [\",mask ^ (1 << i),\"]: \", \"pos:\",c,\" seat:\",i+1 )\n",
    "                        dp[mask] = dp[mask]+dp[mask ^ (1 << i)]\n",
    "        print(dp)\n",
    "        return dp[(1 << n) - 1]  # f[\"11111111\"]即为最后的结果\n",
    "\n",
    "    def countArrangement1(self, n: int) -> int:\n",
    "\n",
    "        dp=[0 for i in range(n+1)]\n",
    "        tot=0\n",
    "\n",
    "        def dfs(seat:int, num:int):\n",
    "            nonlocal tot\n",
    "            if seat==n:\n",
    "                tot+=1\n",
    "#                print(dp)\n",
    "                return\n",
    "\n",
    "            dp[num]=seat\n",
    "            for i in range(1,n+1):\n",
    "                if dp[i]==0:\n",
    "                    if i%(seat+1)==0 or (seat+1)%i==0:\n",
    "                        dfs(seat+1,i)\n",
    "            dp[num] = 0\n",
    "\n",
    "        for i in range(1,n+1):\n",
    "            dfs(1,i)\n",
    "\n",
    "        return tot\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countArrangement(self, n: int) -> int:\n",
    "        mm,ss=[1<<x for x in range(n)],1<<n\n",
    "        dp,ndp=[1]+[0]*ss,[0]*ss\n",
    "        for nn in range(n):\n",
    "            for i,s in ((i,sum(x)) for i in range(n) for x in combinations(mm[:i]+mm[i+1:],nn)):ndp[mm[i]+s]+=dp[s] if (i+1)%(nn+1)==0 or (nn+1)%(i+1)==0 else 0\n",
    "            dp,ndp=ndp,[0]*ss\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countArrangement(self, n: int) -> int:\n",
    "        canFill = defaultdict(list)\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(1, n+1):\n",
    "                # 每个位置可以填入哪些数\n",
    "                if j % i == 0 or i % j == 0:\n",
    "                    canFill[i].append(j-1)\n",
    "        # 根据可填入数字的个数排序，优先填入个数少的\n",
    "        order = sorted(canFill.keys(), key=lambda x:len(canFill[x]))\n",
    "        end = (1 << n) - 1\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(state):\n",
    "            # 全部填入\n",
    "            if state == end:\n",
    "                return 1\n",
    "            cnts = ans = 0\n",
    "            # 当前该填第几个位置\n",
    "            for i in range(n):\n",
    "                if (1 << i) & state:\n",
    "                    cnts += 1\n",
    "            # 当前位置可以填哪些数\n",
    "            for i in canFill[order[cnts]]:\n",
    "                # 哪些数还没被填\n",
    "                if not ((1 << i) & state):\n",
    "                    ans += dfs(state ^ (1 << i))\n",
    "            return ans\n",
    "        \n",
    "        return dfs(0)\n",
    "\n",
    "# 作者：Benhao\n",
    "# 链接：https://leetcode.cn/problems/beautiful-arrangement/solutions/938022/python-ji-yi-hua-di-gui-or-zhuang-tai-ya-zuss/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countArrangement(self, n: int) -> int:\n",
    "        D = {(1 << i) : i for i in range(15)}\n",
    "        def remain(left):\n",
    "            ans = []\n",
    "            while left:\n",
    "                tmp = left & (-left)\n",
    "                ans.append(D[tmp] + 1)\n",
    "                left -= tmp\n",
    "            return ans\n",
    "\n",
    "        @cache\n",
    "        def dfs(i, left):\n",
    "            if not left:\n",
    "                return 1\n",
    "            L = remain(left)\n",
    "            ans = 0\n",
    "            for e in L:\n",
    "                if e % nums[i] == 0 or nums[i] % e == 0:\n",
    "                    ans += dfs(i + 1, left ^ (1 << (e - 1)))\n",
    "            return ans\n",
    "\n",
    "        L = list(range(n, 0, -1))\n",
    "        prime = []\n",
    "        nonprime = []\n",
    "        for e in L:\n",
    "            for i in range(2, int(e ** 0.5) + 1):\n",
    "                if e % i == 0:\n",
    "                    nonprime.append(e)\n",
    "                    break\n",
    "            else:\n",
    "                prime.append(e)\n",
    "        nums = prime + nonprime\n",
    "        return dfs(0, (1 << n) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def countArrangement(self, n: int) -> int:\r\n",
    "        ans = []\r\n",
    "        def dfs(current_pos, current_list):\r\n",
    "            if current_pos == n:\r\n",
    "                ans.append(1)\r\n",
    "                return\r\n",
    "            for i in range(1, n + 1):\r\n",
    "                if i in current_list:\r\n",
    "                    continue\r\n",
    "                if (current_pos + 1) % i == 0 or i % (current_pos + 1) == 0:\r\n",
    "                    current_list.append(i)\r\n",
    "                    dfs(current_pos + 1, current_list)\r\n",
    "                    current_list.pop()\r\n",
    "        dfs(0,[])\r\n",
    "        return sum(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def countArrangement(self, n: int) -> int:\n",
    "        \n",
    "        dic = defaultdict(list)\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                if not i % j or not j % i:\n",
    "                    dic[i].append(j)\n",
    "        less_to_more = sorted(dic, key = lambda x: len(dic[x]))\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def findBeauty(l, n):\n",
    "            if not l:\n",
    "                return 1\n",
    "            ans = 0\n",
    "            for i in dic[less_to_more[n]]:\n",
    "                if i in l:\n",
    "                    tmp = list(l)\n",
    "                    tmp.remove(i)\n",
    "                    ans += findBeauty(tuple(tmp), n + 1)\n",
    "            return ans\n",
    "\n",
    "        l = tuple(i for i in range(1, n + 1))\n",
    "        return findBeauty(l, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def countArrangement(self, n: int) -> int:\n",
    "        \n",
    "        dic = defaultdict(list)\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                if not i % j or not j % i:\n",
    "                    dic[i].append(j)\n",
    "        less_to_more = sorted(dic, key = lambda x: len(dic[x]))\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def findBeauty(l, n):\n",
    "            if not l:\n",
    "                return 1\n",
    "            ans = 0\n",
    "            for i in dic[less_to_more[n]]:\n",
    "                if i in l:\n",
    "                    tmp = list(l)\n",
    "                    tmp.remove(i)\n",
    "                    ans += findBeauty(tuple(tmp), n + 1)\n",
    "            return ans\n",
    "\n",
    "        l = tuple(i for i in range(1, n + 1))\n",
    "        return findBeauty(l, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "canfill = [0] * 15  # 每个位置可以填入哪些数 -1处理\n",
    "for i in range(15):\n",
    "    for j in range(15):\n",
    "        if (i + 1) % (j + 1) == 0 or (j + 1) % (i + 1) == 0:\n",
    "            canfill[i] |= 1 << j\n",
    "\n",
    "class Solution:\n",
    "    def countArrangement(self, n: int) -> int:\n",
    "        # 前i个位置 放数字集合sta的方法数  （sta大小-1就是i）\n",
    "        # 最后一个位置放 j j属于sta 那么子问题是 前i-1个位置 放数字 sta^j的方法数\n",
    "        u = (1 << n) - 1\n",
    "        @lru_cache(None)\n",
    "        def dfs(sta): # 前i个位置\n",
    "            if sta == 0:\n",
    "                return 1\n",
    "            i = sta.bit_count() - 1\n",
    "            ans = 0\n",
    "            for j in range(n):\n",
    "                if sta >> j & 1 and canfill[i] >> j & 1:\n",
    "                    ans += dfs(sta ^ (1 << j))\n",
    "            return ans\n",
    "        return dfs(u)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countArrangement(self, n: int) -> int:\n",
    "        dst = (1 << n) - 1\n",
    "        cache = {}\n",
    "        exp_index = collections.defaultdict(list)\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(1, n+1):\n",
    "                if i % j == 0 or j % i == 0:\n",
    "                    exp_index[i].append(j-1)\n",
    "\n",
    "\n",
    "        def dfs(level, state, count):\n",
    "            if state in cache:\n",
    "                return cache[state]\n",
    "            if level == n + 1:\n",
    "                if state == dst:\n",
    "                    return count + 1\n",
    "                return count\n",
    "            new = 0\n",
    "            for i in exp_index[level]:\n",
    "                tmp = state >> i\n",
    "                if tmp & 1 == 0:\n",
    "                    new += dfs(level + 1, state | (1 << i), count)\n",
    "            cache[state] = new + count\n",
    "            return new + count\n",
    "\n",
    "        r = dfs(1, 0, 0)\n",
    "\n",
    "        return r\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 2.使用helper(i,num_tuple)函数\n",
    "class Solution:\n",
    "    def countArrangement(self, n: int) -> int:\n",
    "        '''\n",
    "        求解思路:\n",
    "        使用函数helper(i, num_tuple)，其中：i 是数字下标 num_tuple 数据列表\n",
    "\n",
    "        1.获取数字满足优美的排列的判断条件的能插入的全部位置\n",
    "            helper(n, tuple(range(1, n + 1)))\n",
    "        2.当前n满足优美的排列的判断条件\n",
    "            num_tuple[j] % i == 0 or i % num_tuple[j] == 0\n",
    "        3.求解子问题的结果\n",
    "            helper(i - 1, num_tuple[:j] + num_tuple[j + 1:])\n",
    "        4.由于求解子问题的过程存在很多重复计算，可以使用 lru_cache 缓存来加速算法\n",
    "        '''\n",
    "        return self.helper(n, tuple(range(1, n + 1)))\n",
    "\n",
    "    # 缓存数据加速算法\n",
    "    @lru_cache(maxsize=None, typed=False)\n",
    "    def helper(self, i, num_tuple) -> int:\n",
    "        # 子问题退出的条件\n",
    "        if i == 1:\n",
    "            return 1\n",
    "        res = 0\n",
    "        for j in range(len(num_tuple)):\n",
    "            if num_tuple[j] % i == 0 or i % num_tuple[j] == 0:\n",
    "                res += self.helper(i - 1, num_tuple[:j] + num_tuple[j + 1:])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countArrangement(self, n: int) -> int:\n",
    "        #基于宫水三叶思路的解法\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i,state):\n",
    "            if i==0:\n",
    "                return 1\n",
    "            ans=0\n",
    "            for k in range(1,n+1):\n",
    "                if (k%i==0 or i%k==0) and state>>(k-1)&1:\n",
    "                    ans+=dfs(i-1,state&(~(1<<(k-1))))\n",
    "            return ans\n",
    "        state=1<<n\n",
    "        return dfs(n,state-1)\n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        #自己的朴素解法\n",
    "        # ans=0\n",
    "        # def dfs(i,temp):\n",
    "        #     nonlocal ans\n",
    "        #     if i<0:\n",
    "        #         ans+=1\n",
    "        #         return\n",
    "        #     for j,x in enumerate(temp):\n",
    "        #         if x%(i+1)==0 or (i+1)%x==0:\n",
    "        #             dfs(i-1,temp[:j]+temp[j+1:])\n",
    "        #     return \n",
    "        \n",
    "        # dfs(n-1,list(range(1,n+1)))\n",
    "        # return ans\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countArrangement(self, n: int) -> int:\n",
    "        @cache\n",
    "        def count(s):\n",
    "            if s.count('1') == 0:\n",
    "                return 1\n",
    "            else:\n",
    "                pos = s.count('1')\n",
    "                ans = 0\n",
    "                for i in range(n):\n",
    "                    if s[i] == '1' and ((i+1) % pos == 0 or pos % (i+1) == 0):\n",
    "                        ans += count(s[:i] + '0' + s[i+1:])\n",
    "                return ans\n",
    "        return count('1' * n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countArrangement(self, n: int) -> int:\n",
    "        @cache\n",
    "        def dfs(u, mask):\n",
    "            if u == 0:return 1\n",
    "            res = 0\n",
    "            for i in range(n):\n",
    "                if (mask >> i & 1) and ((i + 1) % u == 0 or u % (i + 1) == 0):\n",
    "                    res += dfs(u - 1, mask ^ (1 << i))\n",
    "            return res\n",
    "        return dfs(n, (1 << n) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 类似题目 698. 划分为k个相等的子集 https://leetcode.cn/problems/partition-to-k-equal-sum-subsets/\n",
    "    # 473. 火柴拼正方形 https://leetcode.cn/problems/matchsticks-to-square/submissions/\n",
    "    # 464. 我能赢吗 https://leetcode.cn/problems/can-i-win/\n",
    "    def countArrangement(self, n: int) -> int:\n",
    "        m = (1 << (n + 1)) - 1 # 下标从 1 开始 \n",
    "        @cache\n",
    "        def dfs(used):\n",
    "            if used == m: return 1\n",
    "            res = 0\n",
    "            for num in range(1, n + 1): # used.bit_count() 为将要放置num的索引\n",
    "                if used & (1 << num) == 0 and (num % used.bit_count() == 0 or used.bit_count() % num == 0):\n",
    "                    res += dfs(used | (1 << num))\n",
    "            return res\n",
    "        # 因为下标从1开始, used的第一个二进制位没有用,\n",
    "        # 因为used.bit_count() 为将要放置num的索引,used必须初始化为1, 否则 要used.bit_count() - 1 ,\n",
    "        # 但是used=0,used.bit_count()=0, 会出现mod 0 的异常, 所以used从1开始\n",
    "        return dfs(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countArrangement(self, n: int) -> int:\n",
    "        # d[mask], (mask >> (i - 1)) 为 1 表示数组里已经有 i 了\n",
    "        d = defaultdict(int)\n",
    "        d[0] = 1\n",
    "        for mask in range(1 << n):\n",
    "            cnt = bin(mask).count('1') + 1\n",
    "            for i in range(1, n + 1):\n",
    "                if (mask >> (i - 1)) & 1 == 0 and (i % cnt == 0 or cnt % i == 0):\n",
    "                    d[mask | (1 << (i - 1))] += d[mask]\n",
    "        # print(d)\n",
    "        return d[(1 << n) - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countArrangement(self, n: int) -> int:\n",
    "        dp = [0] * (1 << n)\n",
    "        dp[0] = 1\n",
    "        cnt = {0:0}\n",
    "        for i in range(1, 1 << n):\n",
    "            cnt[i] = cnt[i >> 1] + (i & 1)\n",
    "\n",
    "        for i in range((1 << n) - 1):\n",
    "            if not dp[i]: continue\n",
    "            idx = cnt[i]\n",
    "            idx += 1\n",
    "            for j in range(n):\n",
    "                if (idx % (j+1) == 0 or (j+1) % idx == 0) and not i >> j & 1:\n",
    "                    dp[i | 1 << j] += dp[i]\n",
    "        return dp[-1]\n",
    "\n",
    "        # visted = [0] * n\n",
    "        # def dfs(idx):\n",
    "        #     if idx == n+1: return 1\n",
    "        #     ret = 0\n",
    "        #     for i in range(n):\n",
    "        #         if not visted[i] and ((i+1) % idx == 0 or (idx) % (i+1) == 0):\n",
    "        #             visted[i] = 1\n",
    "        #             ret += dfs(idx + 1)\n",
    "        #             visted[i] = 0\n",
    "        #     return ret\n",
    "        # return dfs(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countArrangement(self, n: int) -> int:\n",
    "\n",
    "        # perm[i] % i ==0 or i % perm[i] == 0\n",
    "\n",
    "        def get_one_cnt(state):\n",
    "            cnt = 0\n",
    "            while state != 0:\n",
    "                state -= state & (-state)\n",
    "                cnt += 1\n",
    "            \n",
    "            return cnt\n",
    "\n",
    "        mask = 1 << n\n",
    "\n",
    "        dp = defaultdict(lambda : 0)\n",
    "        dp[0] = 1\n",
    "\n",
    "        for state in range(1, mask):\n",
    "            one_cnt = get_one_cnt(state)\n",
    "\n",
    "            for i in range(n):\n",
    "                \n",
    "                if (state >> i) & 1 == 0:\n",
    "                    continue\n",
    "                \n",
    "                if (i+1) % one_cnt != 0 and one_cnt % (i+1) != 0:\n",
    "                    continue\n",
    "                \n",
    "                pre_state = state & (~(1 << i))\n",
    "                # print(\"state: {0:b}\".format(state))\n",
    "                # print(\"pre_state: {0:b}\".format(pre_state))\n",
    "                dp[state] += dp[pre_state]\n",
    "\n",
    "        # print(dp)\n",
    "        return dp[mask-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countArrangement(self, n: int) -> int:\n",
    "        # 回溯\n",
    "        # def bt(indx: int):\n",
    "        #     if indx == n+1:\n",
    "        #         nonlocal num\n",
    "        #         num += 1\n",
    "        #         return \n",
    "            \n",
    "        #     for x in match[indx]:\n",
    "        #         if  x not in vis:\n",
    "        #             vis.add(x)\n",
    "        #             bt(indx+1)\n",
    "        #             vis.discard(x)  # 恢复现场\n",
    "            \n",
    "        # num = 0\n",
    "        # vis = set()\n",
    "        \n",
    "        # match = defaultdict(list)\n",
    "        # for i in range(1, n+1):\n",
    "        #     for j in range(1, n+1):\n",
    "        #         if i % j == 0 or j % i == 0:\n",
    "        #             match[i].append(j)\n",
    "        # bt(1)\n",
    "        # return num\n",
    "\n",
    "\n",
    "        # dp + 状态压缩\n",
    "        # states = 1 << n\n",
    "        # dp = [0 for _ in range(states)]\n",
    "        # dp[0] = 1\n",
    "\n",
    "        # for state in range(states):                         # 枚举所有状态\n",
    "        #     one_num = bin(state).count(\"1\")                 # 计算当前状态中选择了多少个数字（即统计 1 的个数）\n",
    "        #     for k in range(1, n + 1):                       # 枚举最后 1 位上所选的数字\n",
    "        #         if state >> (k - 1) & 1 == 0:               # 只有 state 第 k 个位置上为 1 才表示选了该数字\n",
    "        #             continue\n",
    "        #         if one_num % k == 0 or k % one_num == 0:    # 只有满足整除关系才符合要求\n",
    "        #             # dp[state] 由前 one_num - 1 个位置，且 state 第 k 位为 0 的状态而来\n",
    "        #             dp[state] += dp[state ^ (1 << (k - 1))]\n",
    "\n",
    "        # return dp[states - 1]\n",
    "\n",
    "\n",
    "\n",
    "        # 回溯\n",
    "        @cache\n",
    "        def bt(i, num_tuple):\n",
    "            # 边界条件\n",
    "            if i == 1:\n",
    "                return 1\n",
    "            res = 0\n",
    "            for j in range(len(num_tuple)):\n",
    "                if num_tuple[j] % i == 0 or i % num_tuple[j] == 0:\n",
    "                    # 去掉j再继续递归下去\n",
    "                    res += bt(i-1, num_tuple[:j] + num_tuple[j+1:]) \n",
    "            return res\n",
    "            \n",
    "        return bt(n, tuple(range(1, n+1)))\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countArrangement(self, n: int) -> int:\n",
    "        def dfs(i,lis):\n",
    "            if tuple(lis) in cache:\n",
    "                return cache[tuple(lis)]\n",
    "            if i==n:\n",
    "                if lis[0]%i == 0 or i%lis[0] == 0:\n",
    "                    res = 1\n",
    "                else:\n",
    "                    res = 0\n",
    "            else:\n",
    "                res = 0\n",
    "                for j,m in enumerate(lis):\n",
    "                    if m%i == 0 or i%m == 0:\n",
    "                        res+=dfs(i+1,lis[:j]+lis[j+1:])\n",
    "            cache[tuple(lis)] = res\n",
    "            return res\n",
    "        cache={}\n",
    "        return dfs(1,[i for i in range(1,n+1)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countArrangement(self, n: int) -> int:\n",
    "        # 缓存数据加速算法\n",
    "        @lru_cache(maxsize=None, typed=False)\n",
    "        def helper(i, num_tuple):\n",
    "            # 子问题的退出条件\n",
    "            if i == 1:\n",
    "                return 1\n",
    "            res = 0\n",
    "            for j in range(len(num_tuple)):\n",
    "                if num_tuple[j] % i == 0 or i % num_tuple[j] == 0:\n",
    "                    res += helper(i - 1, num_tuple[:j] + num_tuple[j + 1:])\n",
    "            return res\n",
    "\n",
    "        return helper(n, tuple(range(1, n + 1)))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countArrangement(self, n: int) -> int:\n",
    "        # dp[m][state]: 表示只使用数字1~m在 state标记所表示的perm的位置条件下的优美的排列数目,\n",
    "        # 若当 state=2^i1+2^i2+...+2^ik (k=m-1)表示只在perm[]的i1,i2,...,ik的下标中排列；\n",
    "        # 特别地当 state=0 时，perm数组为空，排列列数目算作1。（尽管不算优美的排列，而只是类似0的阶乘那样作为临界值）。\n",
    "        dp = [[0] * (1 << n) for i in range(n+1)]\n",
    "        dp[0][0]=1\n",
    "        for i in range(1, n + 1):\n",
    "            for state in range(0, 1 << n):\n",
    "                if 0==dp[i-1][state]:continue\n",
    "                for j in range(n):\n",
    "                    if 0 == (state & (1 << j)) and (0==i % (j + 1)or 0== (j + 1) % i):\n",
    "                        dp[i][state | (1 << j)] += dp[i-1][state]\n",
    "        # print(dp)\n",
    "        return dp[-1][-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countArrangement(self, n: int) -> int:\n",
    "        # 如何想到dp, 因为求排列就是一个回溯问题，本题是求符合要求的排列数量\n",
    "        @cache\n",
    "        def dfs(i): # i：可选数的集合\n",
    "            if i == 0: return 1\n",
    "            res = 0\n",
    "            for j in range(n): # 枚举选哪个\n",
    "                # perm[i]能被i整除  => (j+1) % (n-i.bit_count()+1) == 0\n",
    "                # i能被perm[i]整除  => (n-i.bit_count()+1) % (j+1) == 0\n",
    "                if ((i >> j) & 1) and ((j+1) % (n-i.bit_count()+1) == 0 or (n-i.bit_count()+1) % (j+1) == 0):\n",
    "                    res += dfs(i ^ (1 << j))\n",
    "            return res\n",
    "        return dfs((1 << n) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countArrangement(self, n: int) -> int:\n",
    "        def dfs(i, visted):\n",
    "            if i > n:\n",
    "                return 1\n",
    "            if i in memo and visted in memo[i]:\n",
    "                return memo[i][visted]\n",
    "            res = 0\n",
    "            for j in range(1, n + 1):\n",
    "                if (((1 << j) & visted) == 0) and (i % j == 0 or j % i == 0):\n",
    "                    res += dfs(i + 1, ((1 << j) | visted))\n",
    "\n",
    "            memo[i][visted] = res\n",
    "            return res\n",
    "\n",
    "        memo = [collections.defaultdict(list) for _ in range(n + 1)]\n",
    "        # memo = [[-1] * (1 << n) for _ in range(n + 1)]\n",
    "        return dfs(1, 0)\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def countArrangement(self, n: int) -> int:\n",
    "#         dp = [0] * (1 << n)\n",
    "#         dp[0] = 1\n",
    "#         print(dp)\n",
    "#         for mask in range(1, 1 << n):\n",
    "#             num = bin(mask).count(\"1\")\n",
    "#             print(mask, bin(mask), num)\n",
    "#             for i in range(n):\n",
    "#                 print(\"  \", i, 1 << i)\n",
    "#                 if mask & (1 << i) and (num % (i + 1) == 0 or (i + 1) % num == 0):\n",
    "#                     dp[mask] += dp[mask ^ (1 << i)]\n",
    "#         # return dp[(1 << n) - 1]\n",
    "#         return dp[-1]\n",
    "\n",
    "\n",
    "# dfs\n",
    "# class Solution:\n",
    "#     def countArrangement(self, n: int) -> int:\n",
    "#         def dfs(i, visited):\n",
    "#             if i > n:\n",
    "#                 return 1\n",
    "#             res = 0\n",
    "#             for j in range(1, n + 1):\n",
    "#                 if ((1 << j) & visited) == 0 and (j % i == 0 or i % j == 0):\n",
    "#                     res += dfs(i + 1, (1 << j) | visited)\n",
    "#             return res\n",
    "#         return dfs(1, 0)\n",
    "\n",
    "# dfs\n",
    "# class Solution:\n",
    "#     def countArrangement(self, n: int) -> int:\n",
    "#         def dfs(i, visited):\n",
    "#             if i > n:\n",
    "#                 return 1\n",
    "#             res = 0\n",
    "#             for j in range(1, n + 1):\n",
    "#                 if (j not in visited or not visited[j]) and (j % i == 0 or i % j == 0):\n",
    "#                     visited[j] = True\n",
    "#                     res += dfs(i + 1, visited)\n",
    "#                     visited[j] = False\n",
    "#             return res\n",
    "#         return dfs(1, {})\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countArrangement(self, n: int) -> int:\n",
    "        # 如何想到dp, 因为求排列就是一个回溯问题，本题是求符合要求的排列数量,存在重复子问题，想到状压dp\n",
    "        @cache\n",
    "        def dfs(i): # i：可选数的集合\n",
    "            if i == 0: return 1\n",
    "            res = 0\n",
    "            for j in range(n): # 枚举选哪个\n",
    "                # perm[i]能被i整除  => (j+1) % (n-i.bit_count()+1) == 0\n",
    "                # i能被perm[i]整除  => (n-i.bit_count()+1) % (j+1) == 0\n",
    "                if ((i >> j) & 1) and ((j+1) % (n-i.bit_count()+1) == 0 or (n-i.bit_count()+1) % (j+1) == 0):\n",
    "                    res += dfs(i ^ (1 << j))\n",
    "            return res\n",
    "        return dfs((1 << n) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countArrangement(self, n: int) -> int:\n",
    "        u = (1 << n) - 1\n",
    "\n",
    "        @cache\n",
    "        def dfs(k: int) -> int:\n",
    "            if k == 0:\n",
    "                return 1\n",
    "            res = 0\n",
    "            i = n - bin(k).count('1') + 1  # i 代表该填哪个位置了\n",
    "            for j in range(1, n + 1):\n",
    "                if k & (1 << (j - 1)) and ((i % j == 0) or (j % i == 0)):\n",
    "                    res += dfs(k ^ (1 << (j - 1)))\n",
    "            return res\n",
    "\n",
    "        return dfs(u)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "canfill = [0] * 15  # 每个位置可以填入哪些数 -1处理\n",
    "for i in range(15):\n",
    "    for j in range(15):\n",
    "        if (i + 1) % (j + 1) == 0 or (j + 1) % (i + 1) == 0:\n",
    "            canfill[i] |= 1 << j\n",
    "\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def countArrangement(self, n: int) -> int:\n",
    "        u = (1 << n) - 1\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(sta):  # [0:n]范围构造 已选位置 方案数\n",
    "            i = sta.bit_count()\n",
    "            if i == n: return 1\n",
    "            ans = 0\n",
    "            cf = (u ^ sta) & canfill[i]\n",
    "            while cf:\n",
    "                lb = cf & -cf\n",
    "                ans += dfs(sta | lb)\n",
    "                cf ^= lb\n",
    "            return ans\n",
    "\n",
    "        return dfs(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countArrangement(self, n: int) -> int:\n",
    "        f = [[0] * (1 << n) for _ in range(n + 1)]\n",
    "        # f[s][i] 表示s状态下，填充第i个位置的方法数\n",
    "        f[0][0] = 1\n",
    "        for i in range(1 << n):\n",
    "            cnt = i.bit_count()\n",
    "            for j in range(n): \n",
    "                if i >> j & 1==0 and ((cnt + 1) % (j + 1) == 0 or (j + 1) % (cnt + 1) == 0):\n",
    "                    f[cnt + 1][i | 1 << j] += f[cnt][i]\n",
    "        return f[n][-1]\n",
    "\n",
    "        # @cache\n",
    "        # def dfs(i: int, vis: int): \n",
    "        #     if i == n:\n",
    "        #         return 1\n",
    "        #     ans = 0\n",
    "        #     for j in range(n):\n",
    "        #         if vis >> j & 1 == 0 and ((j + 1) % (i + 1) == 0 or (i + 1) % (j + 1) == 0):\n",
    "        #                     ans += dfs(i + 1, vis | 1 << j)\n",
    "        #     return ans\n",
    "        return dfs(0, 0)\n",
    "                            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countArrangement(self, n: int) -> int:\n",
    "        @cache\n",
    "        def dfs(i: int, used: int) -> int:\n",
    "            if i > n:\n",
    "                return 1\n",
    "            \n",
    "            cnt = 0\n",
    "            for j in range(1, n+1):\n",
    "                if used & 1<<(j-1) != 0:\n",
    "                    continue\n",
    "                if j % i == 0 or i % j == 0:\n",
    "                    cnt += dfs(i+1, used | 1<<(j-1))\n",
    "            return cnt\n",
    "        return dfs(1, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countArrangement(self, n: int) -> int:\n",
    "        table = [[] for _ in range(n+1)]\n",
    "        for a in range(1, n + 1):\n",
    "            table[a].append(a)\n",
    "            b = 2 * a\n",
    "            while b <= n:\n",
    "                table[a].append(b)\n",
    "                table[b].append(a)\n",
    "                b += a\n",
    "        @cache\n",
    "        def DFS(i, numbers):\n",
    "            if i == n + 1:\n",
    "                return 1\n",
    "            ret = 0\n",
    "            possibles = table[i]\n",
    "            for p in possibles:\n",
    "                if (1 << p) & numbers:\n",
    "                    ret += DFS(i + 1, (1 << p) ^ numbers)\n",
    "            return ret\n",
    "        return DFS(1, (1 << n + 1) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countArrangement(self, n: int) -> int:\n",
    "        @cache\n",
    "        def dfs(i: int, used: int) -> int:\n",
    "            if i>n:\n",
    "                return 1\n",
    "            \n",
    "            cnt = 0\n",
    "            for j in range(1, n+1):\n",
    "                if used & 1<<(j-1) != 0:\n",
    "                    continue\n",
    "                if j % i == 0 or i % j == 0:\n",
    "                    cnt += dfs(i+1, used | 1<<(j-1))\n",
    "            return cnt\n",
    "        return dfs(1, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countArrangement(self, n: int) -> int:\n",
    "        mask = (1 << n) - 1\n",
    "        @cache\n",
    "        def dfs(i,mask):\n",
    "            if i == n:\n",
    "                return int(mask == 0)\n",
    "            ans = 0\n",
    "            for j in range(n):\n",
    "                if (mask >> j) & 1:\n",
    "                    if (i + 1) % (j + 1) == 0 or (j + 1) % (i + 1) == 0:\n",
    "                        ans += dfs(i + 1,mask & ((1 << n) - 1) ^ (1 << j))\n",
    "            return ans\n",
    "        return dfs(0,mask)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def countArrangement(self, n: int) -> int:\r\n",
    "        self.ans = []\r\n",
    "        self.used = [False] * (n+1)\r\n",
    "        self.backtrack(n, [])\r\n",
    "        return len(self.ans)\r\n",
    "\r\n",
    "    def backtrack(self, n, path):\r\n",
    "        if len(path) >= n:\r\n",
    "            if self.perfect(path):\r\n",
    "                self.ans.append(path)\r\n",
    "            return\r\n",
    "        \r\n",
    "        for i in range(1, n+1):\r\n",
    "            if self.used[i]:\r\n",
    "                continue\r\n",
    "            \r\n",
    "            if not self.perfect(path):\r\n",
    "                break\r\n",
    "            \r\n",
    "            self.used[i] = True\r\n",
    "            self.backtrack(n, path+[i])\r\n",
    "            self.used[i] = False\r\n",
    "        \r\n",
    "    def perfect(self, nums):\r\n",
    "        for i, val in enumerate(nums):\r\n",
    "            i += 1\r\n",
    "            if not (val % i == 0 or i % val == 0):\r\n",
    "                return False\r\n",
    "        \r\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countArrangement(self, n: int) -> int:\n",
    "        dp = {}\n",
    "        def dfs(cur, visited):\n",
    "            if cur > n:\n",
    "                return 1\n",
    "            if not dp.get((cur, visited), None) == None:\n",
    "                return dp.get((cur, visited))\n",
    "            res = 0\n",
    "            for i in range(1, n + 1):\n",
    "                if (visited >> i) & 1 or (i % cur and cur % i):\n",
    "                    continue\n",
    "                res += dfs(cur + 1, visited | (1 << i))\n",
    "            dp[(cur, visited)] = res\n",
    "            return res\n",
    "        return dfs(1, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countArrangement(self, n: int) -> int:\n",
    "        \n",
    "\n",
    "        @cache\n",
    "        def dfs(finded, i):\n",
    "            if i == n + 1:\n",
    "                return 1\n",
    "            ans = 0\n",
    "            for num in range(n):\n",
    "                if (finded >> num) & 1 == 0 and ((num + 1) % i == 0 or i % (num + 1) == 0):\n",
    "                    finded |= (1 << num)\n",
    "                    ans += dfs(finded, i + 1)\n",
    "                    finded ^= (1 << num)\n",
    "            return ans\n",
    "\n",
    "        return dfs(0, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countArrangement(self, n: int) -> int:\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(i,st):\n",
    "            if i == n + 1:\n",
    "                return int(st == 0)\n",
    "            ans = 0\n",
    "            for j in range(n):\n",
    "                if st >> j & 1 and (((j + 1) % i == 0) or (i % (j + 1) == 0)):\n",
    "                    ans += dfs(i + 1,st ^(1 << j))\n",
    "            return ans\n",
    "\n",
    "\n",
    "        return dfs(1,(1 << n) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countArrangement(self, n: int) -> int:\n",
    "        MASK = 2**n-1\n",
    "        @cache\n",
    "        def dfs(i,mask):\n",
    "            # print(i,bin(mask))\n",
    "            if mask==0:\n",
    "                return 1\n",
    "            cdd = mask\n",
    "            idx = 1\n",
    "            ans = 0\n",
    "            while cdd>0:\n",
    "                if cdd&1==1 and (idx%i==0 or i%idx==0):\n",
    "                    ans+=dfs(i+1,mask^(1<<(idx-1)))\n",
    "                idx+=1 \n",
    "                cdd = cdd>>1 \n",
    "            return ans \n",
    "        return dfs(1,MASK)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countArrangement(self, n: int) -> int:\n",
    "        mask =1<<n\n",
    "        dp = [[0]*mask for _ in range(n+1)]\n",
    "        dp[0][0]=1\n",
    "\n",
    "        for i in range(1,n+1):\n",
    "            for visited in range(mask):\n",
    "                for num in range(1,n+1):\n",
    "                    if visited&(1<<(num-1)) and (i % num  ==0  or num % i ==0):\n",
    "                        dp[i][visited] += dp[i-1][visited&(~(1<<(num-1)))]\n",
    "\n",
    "        return dp[n][mask-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countArrangement(self, n: int) -> int:\n",
    "        mask = 1 << n\n",
    "        f = [[0] * mask for i in range(n + 1)]\n",
    "        f[0][0] = 1\n",
    "\n",
    "        for i in range(1, n + 1):\n",
    "            for state in range(mask):\n",
    "                for k in range(1, n + 1):\n",
    "                    if (state >> (k - 1)) & 1 == 0:\n",
    "                        continue\n",
    "                    if k % i != 0 and i % k != 0:\n",
    "                        continue\n",
    "                    f[i][state] += f[i - 1][state & ( ~ (1 << (k - 1)))]\n",
    "        return f[i][mask - 1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countArrangement(self, n: int) -> int:\n",
    "        \"\"\"DP\"\"\"\n",
    "        # state's i-th bit show if a value(i) is used\n",
    "        states = 1 << n\n",
    "        # [0 for _ in range(states)] show all states from 0 to 0...111\n",
    "        dp = [[0 for _ in range(states)] for _ in range(n+1)]\n",
    "        dp[0][0] = 1\n",
    "\n",
    "        for idx in range(1, n+1):\n",
    "        # go through all idx from 1 to n\n",
    "            for msk in range(states):\n",
    "            # go through all state from 0 to 0...111\n",
    "                if bin(msk).count('1') != idx:\n",
    "                # check if the msk match idx first\n",
    "                    continue\n",
    "                for k in range(1, n+1):\n",
    "                # find k that satisfy 2 conditions\n",
    "                    if msk >> (k-1) & 1 == 0:\n",
    "                    # 1st: k should be exist and corresponding msk is valid\n",
    "                        continue\n",
    "                    \n",
    "                    if k % idx == 0 or idx % k == 0:\n",
    "                    # 2nd reason to check if it's valid\n",
    "                        # add up all possible pre-state that satisfy current state(msk)\n",
    "                        dp[idx][msk] += dp[idx - 1][msk ^ (1 << (k-1))]\n",
    "        # aka retuen dp[n][state - 1]\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countArrangement(self, n: int) -> int:\n",
    "        ans = 0\n",
    "        visited = set()\n",
    "\n",
    "        def backtracking(index):\n",
    "            nonlocal ans\n",
    "            if index == n + 1:\n",
    "                ans += 1 ### 排列完一次就会升级一次答案\n",
    "                return\n",
    "\n",
    "            for i in range(1, n + 1):\n",
    "                if i in visited:\n",
    "                    continue\n",
    "                if i % index == 0 or index % i == 0:\n",
    "                    visited.add(i)\n",
    "                    backtracking(index + 1)\n",
    "                    visited.remove(i)\n",
    "\n",
    "        backtracking(1)\n",
    "        return ans\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countArrangement(self, n: int) -> int:\n",
    "        states = 1 << n\n",
    "        dp = [[0 for _ in range(states)] for _ in range(n + 1)]\n",
    "        dp[0][0] = 1\n",
    "\n",
    "        for i in range(1, n + 1):                   # 枚举第 i 个位置\n",
    "            for state in range(states):             # 枚举所有状态\n",
    "                one_num = bin(state).count(\"1\")     # 计算当前状态中选择了多少个数字（即统计 1 的个数）\n",
    "                if one_num != i:                    # 只有 i 与选择数字个数相同时才能计算\n",
    "                    continue\n",
    "                for k in range(1, n + 1):           # 枚举第 i 个位置（最后 1 位）上所选的数字\n",
    "                    if state >> (k - 1) & 1 == 0:   # 只有 state 第 k 个位置上为 1 才表示选了该数字\n",
    "                        continue\n",
    "                    if k % i == 0 or i % k == 0:    # 只有满足整除关系才符合要求\n",
    "                        # dp[i][state] 由前 i - 1 个位置，且 state 第 k 位为 0 的状态而来\n",
    "                        dp[i][state] += dp[i - 1][state & (~(1 << (k - 1)))]\n",
    "\n",
    "        return dp[i][states - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countArrangement(self, N: int) -> int:\n",
    "        res = [False] * N\n",
    "        ans = []\n",
    "\n",
    "        def dps(ltmp):\n",
    "            if ltmp[-1] % len(ltmp) != 0 and len(ltmp) % ltmp[-1] != 0:\n",
    "                return\n",
    "            if len(ltmp) == N:\n",
    "                ans.append(ltmp[:])\n",
    "            else:\n",
    "                for i in range(N):\n",
    "                    if res[i] == True:\n",
    "                        continue\n",
    "                    res[i] = True\n",
    "                    dps(ltmp + [i + 1])\n",
    "                    res[i] = False\n",
    "        dps([1])\n",
    "        return len(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countArrangement(self, n: int) -> int:\n",
    "        d = {}\n",
    "        for i in range(1,n+1):\n",
    "            d[i] = {}\n",
    "        for i in range(1,n+1):\n",
    "            s = i\n",
    "            while s < n+1:\n",
    "                d[i][s]=0\n",
    "                d[s][i]=0\n",
    "                s += i\n",
    "        # print(d)\n",
    "        choose = []\n",
    "        for i in range(1,n+1):\n",
    "            choose.append(list(d[i].keys()))\n",
    "        # print(choose)\n",
    "\n",
    "        # 1 3 5 7 11 13 \n",
    "        # 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15\n",
    "        # 倍数\n",
    "        # 1->1~15\n",
    "        # 2->2 4 6 8 10 12 14\n",
    "        # 3->3 6 9 12 15\n",
    "        # 4->4 8 12\n",
    "        # 5->5 10 15\n",
    "        # 6->6 12\n",
    "        # 7->7 14\n",
    "        # 8->8\n",
    "        # 9->9\n",
    "        # 10->10\n",
    "        # 11->11\n",
    "        # 12->12\n",
    "        # 13->13\n",
    "        # 14->14\n",
    "        # 15->15\n",
    "        # 约数\n",
    "        # 1->1\n",
    "        # 2->1 2\n",
    "        # 3->1 3\n",
    "        # 4->1 2 4\n",
    "        # 5->1 5\n",
    "        # 6->1 2 3\n",
    "        # 7->1 7\n",
    "        # 8->1 2 4 8\n",
    "        # 9->1 3 9\n",
    "        # 10->1 2 5 10\n",
    "        # 11->1 11\n",
    "        # 12->1 2 3 4 6 12\n",
    "        # 13->1 13\n",
    "        # 14->1 2 7 14\n",
    "        # 15->1 3 5 15\n",
    "\n",
    "        result =[]\n",
    "        # result = 0\n",
    "        # choose = [[],[],..,[]]\n",
    "        def backtrack(path, choose,result):\n",
    "\n",
    "            if len(path)==n:\n",
    "                result.append(path)\n",
    "                # result +=1\n",
    "                return\n",
    "            \n",
    "            cur_choose = choose[len(path)]\n",
    "            cur_choose_diff = list(set(cur_choose).difference(set(path)))\n",
    "            if len(cur_choose_diff) == 0:\n",
    "                return\n",
    "            for i in cur_choose_diff:\n",
    "                newpath = path[:]\n",
    "                newpath.append(i)\n",
    "                backtrack(newpath,choose,result)\n",
    "        backtrack([],choose,result)\n",
    "        return len(result)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countArrangement(self, N: int) -> int:\n",
    "        visited = [False] * N\n",
    "        ans = []\n",
    "        def dfs_helper(temp):\n",
    "            # 对不满足条件的进行剪枝\n",
    "            if temp[-1]%len(temp) !=0 and len(temp)%temp[-1] !=0:\n",
    "                return\n",
    "            if len(temp) == N:\n",
    "               \n",
    "                ans.append(temp[:])\n",
    "            else:\n",
    "                for i in range(N):\n",
    "                    if visited[i] == True:\n",
    "                        continue\n",
    "                    visited[i] = True\n",
    "                    dfs_helper(temp+[i+1])\n",
    "                    visited[i] = False\n",
    "        \n",
    "        dfs_helper([1])\n",
    "        return len(ans)\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countArrangement(self, N: int) -> int:\n",
    "        res = []\n",
    "        def dfs(tmp,vis):\n",
    "            if len(tmp)==N:\n",
    "                res.append(tmp)\n",
    "                return \n",
    "            for i in range(1,N+1):\n",
    "                j = len(tmp)+1\n",
    "                if i not in vis and (i%j==0 or j%i==0):\n",
    "                    vis.add(i)\n",
    "                    dfs(tmp+[i],vis|{i})\n",
    "                    vis.remove(i)\n",
    "        dfs([],set())\n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countArrangement(self, n: int) -> int:\n",
    "        def dfs(res, path, idx):\n",
    "            if idx == n+1:\n",
    "                res.append(path.copy())\n",
    "                return\n",
    "            for i in range(1, n+1):\n",
    "                if i in set(path):\n",
    "                    continue\n",
    "                if i % idx == 0 or idx % i == 0:\n",
    "                    dfs(res, path+[i], idx+1)\n",
    "        res = []\n",
    "        dfs(res, [], 1)\n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countArrangement(self, n: int) -> int:\n",
    "        def dfs(res, path, idx):\n",
    "            if idx == n+1:\n",
    "                res.append(path.copy())\n",
    "                return\n",
    "            for i in range(1, n+1):\n",
    "                if i in path:\n",
    "                    continue\n",
    "                if i % idx == 0 or idx % i == 0:\n",
    "                    dfs(res, path+[i], idx+1)\n",
    "        res = []\n",
    "        dfs(res, [], 1)\n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countArrangement(self, N: int) -> int:\n",
    "        nums = [i+1 for i in range(N)]\n",
    "        res = []\n",
    "        def backtrack(nums,temp):\n",
    "            if not nums and len(temp) == N:\n",
    "                res.append(temp)\n",
    "                return \n",
    "            for i in range(len(nums)):\n",
    "                if not temp:\n",
    "                    backtrack(nums[:i]+nums[i+1:],temp+[nums[i]])\n",
    "                else:\n",
    "                    if nums[i] % (len(nums)+1) == 0 or (len(nums)+1) % nums[i] == 0:\n",
    "                        backtrack(nums[:i]+nums[i+1:],temp+[nums[i]])\n",
    "        backtrack(nums,[])\n",
    "  \n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countArrangement(self, n: int) -> int:\n",
    "        self.ans = []\n",
    "        self.backtrace(n, 1, [])\n",
    "        return len(self.ans)  \n",
    "\n",
    "    def backtrace(self, n:int, idx:int, path):\n",
    "        if idx == n+1:\n",
    "            self.ans.append(path[:])\n",
    "            return \n",
    "        \n",
    "        for v in range(1, n+1):\n",
    "            if v in path:\n",
    "                continue\n",
    "            if idx % v == 0 or v % idx == 0:\n",
    "                path.append(v)\n",
    "                self.backtrace(n, idx+1, path)\n",
    "                path.pop(-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countArrangement(self, n: int) -> int:\n",
    "        def choices(i,pre_state):\n",
    "            if i==1:\n",
    "                return range(1,n+1)\n",
    "            return [i for i in range(1,n+1) if i not in pre_state]\n",
    "\n",
    "        def confict(i, choice, pre_state):\n",
    "            if choice%i==0 or i% choice==0:\n",
    "                return False\n",
    "            return True\n",
    "        \n",
    "        def success(pre_state, **condtions):\n",
    "            if len(pre_state)==condtions['n']:\n",
    "                return True\n",
    "            return False\n",
    "\n",
    "        def dfs(i, pre_state, solutions, **condtions):            \n",
    "            if success(pre_state, **condtions):\n",
    "                solutions.append(pre_state.copy())\n",
    "                return\n",
    "\n",
    "            for choice in choices(i,pre_state):\n",
    "                if confict(i, choice, pre_state): continue\n",
    "                pre_state.append(choice)\n",
    "                dfs(i + 1, pre_state, solutions,**condtions)\n",
    "                pre_state.pop()\n",
    "        res = []\n",
    "        dfs(1,[],res,n=n)\n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countArrangement(self, n: int) -> int:\n",
    "        #f[state][i]  state状态下，最后一个数是i+1的方案数\n",
    "        f=[[0]*n for _ in range(1<<n)]\n",
    "        for state in range(1,1<<n):\n",
    "            cnt=state.bit_count()\n",
    "            for i in range(n):\n",
    "                if state&(1<<i) and ( cnt%(i+1)==0 or (i+1)%cnt==0 ):\n",
    "                    if cnt==1:\n",
    "                        f[state][i]=1\n",
    "                    else:\n",
    "                        for j in range(n):\n",
    "                            if i!=j and state&(1<<j):\n",
    "                                f[state][i]+=f[state^(1<<i)][j]\n",
    "        res=0\n",
    "        for i in range(n):\n",
    "            res+=f[-1][i]\n",
    "        return res\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    #x能被y整除：x%y==0 x是y的倍数\n",
    "    #availNums数组就是一个01 bit stream\n",
    "    #backtrack过程中是基于availNums和index递归\n",
    "    # availNums是当前的状态s，index是当前要放数字的位置i \n",
    "    # dp[s][i]表示前1-(i-1)个数字已经选好，选择的状态记录在s中，dp[s][i]对应了选好第i个数字后优美排列的总数\n",
    "    # dp[s'][i+1]表示前1-(i)个数字已经选好，选择的状态记录在s'中，现在要选第i+1个数组\n",
    "    # dp[s'][i+1]基于dp[s][i]的情况，再添加一个数字num\n",
    "    # num要满足(1)num还没有被选中: 状态s下检查数字k有没有被选中的方法：(s>>k)&1 s是01串，向右移动k位，那么k对应的位变为最低位x，x&1==1说明x是1，表明已经被使用过了，最低位是1一定是奇数\n",
    "    # 判断某个数y的奇偶性：if y&1==1 y是奇数\n",
    "    # 结合一下y=(s>>k) y&1==1说明k已经被选过了，不能再用\n",
    "    # (2)num%(i+1)==0 or (i+1)%num==0\n",
    "    # dp[s'][i+1]就是sum over all num: dp[s V {num} where num not in s and （num%(i+1)==0 or (i+1)%num==0）][i+1]\n",
    "    # s和i是有关系的，s中1的个数为i-1\n",
    "    # 假设n是3，那么s 的范围000-111,全选和全不选 \n",
    "    def countArrangement(self, n: int) -> int:\n",
    "        states=1<<n\n",
    "        dp=[[0]*(n+1) for i in range(0,states)]\n",
    "        dp[0][0]=1 #n=0 一个数字也不选,符合条件的就是空集合s=000\n",
    "        \n",
    "        for s in range(0,states):\n",
    "            i=str(bin(s)).count('1')+1\n",
    "            for k in range(1,n+1): \n",
    "                if (s>>(k-1))&1==1: continue #数字k已经被选过了，不能再用\n",
    "                if k%(i)==0 or (i)%k==0:\n",
    "                    newS=s| (1 << (k - 1))  # 数字 s 的第 k 位设置为1：s = s| (1 << (k - 1)) s=9 1001 k=3 newS=13 1101 \n",
    "                    dp[newS][i]+=dp[s][i-1]  \n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    #x能被y整除：x%y==0 x是y的倍数\n",
    "    #availNums数组就是一个01 bit stream\n",
    "    #backtrack过程中是基于availNums和index递归\n",
    "    # availNums是当前的状态s，index是当前要放数字的位置i \n",
    "    # dp[s][i]表示前1-(i-1)个数字已经选好，选择的状态记录在s中，dp[s][i]对应了选好第i个数字后优美排列的总数\n",
    "    # dp[s'][i+1]表示前1-(i)个数字已经选好，选择的状态记录在s'中，现在要选第i+1个数组\n",
    "    # dp[s'][i+1]基于dp[s][i]的情况，再添加一个数字num\n",
    "    # num要满足(1)num还没有被选中: 状态s下检查数字k有没有被选中的方法：(s>>k)&1 s是01串，向右移动k位，那么k对应的位变为最低位x，x&1==1说明x是1，表明已经被使用过了，最低位是1一定是奇数\n",
    "    # 判断某个数y的奇偶性：if y&1==1 y是奇数\n",
    "    # 结合一下y=(s>>k) y&1==1说明k已经被选过了，不能再用\n",
    "    # (2)num%(i+1)==0 or (i+1)%num==0\n",
    "    # dp[s'][i+1]就是sum over all num: dp[s V {num} where num not in s and （num%(i+1)==0 or (i+1)%num==0）][i+1]\n",
    "    # 假设n是3，那么s 的范围000-111,全选和全不选 \n",
    "    def countArrangement(self, n: int) -> int:\n",
    "        states=1<<n\n",
    "        dp=[[0]*(n+1) for i in range(0,states)]\n",
    "        dp[0][0]=1 #n=0 一个数字也不选,符合条件的就是空集合s=000\n",
    "        \n",
    "        for s in range(0,states):\n",
    "            for i in range(1,n+1):\n",
    "                for k in range(1,n+1): \n",
    "                    if (s>>(k-1))&1==1: continue #数字k已经被选过了，不能再用\n",
    "                    if k%(i)==0 or (i)%k==0:\n",
    "                        newS=s| (1 << (k - 1))  # 数字 s 的第 k 位设置为1：s = s| (1 << (k - 1)) s=9 1001 k=3 newS=13 1101 \n",
    "                        \n",
    "                        dp[newS][i]+=dp[s][i-1]  \n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countArrangement(self, n: int) -> int:\n",
    "        max = 1 << n\n",
    "        dp = [[0 for i in range(1 << n)] for j in range(n + 1)]\n",
    "        dp[0][0] = 1\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(max):\n",
    "                for k in range(1, n + 1):\n",
    "                    if (j >> (k - 1)) != 0:\n",
    "                        if i % k == 0 or k % i == 0:\n",
    "                            dp[i][j] += dp[i - 1][j ^ (1 << (k - 1))]\n",
    "        return dp[n][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from copy import deepcopy\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countArrangement(self, N: int) -> int:\n",
    "        ans = []\n",
    "\n",
    "        def helper(nums: List[int], hub: List[int]):\n",
    "            if len(nums) == 0:\n",
    "                ans.append(deepcopy(hub))\n",
    "                return\n",
    "            for idx, num in enumerate(nums):\n",
    "                i = len(hub) + 1\n",
    "                if i % num == 0 or num % i == 0:\n",
    "                    hub.append(num)\n",
    "                    helper(nums[:idx] + nums[idx + 1:], hub)\n",
    "                    hub.pop()\n",
    "\n",
    "        helper(list(range(1, N + 1)), [])\n",
    "        return len(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countArrangement(self, n: int) -> int:\n",
    "        @cache\n",
    "        def put(i, S):\n",
    "            \"\"\" number of ways to put `perm[i:]` with `S`\"\"\"\n",
    "            if i==n+1: return 1\n",
    "            ret = 0\n",
    "            for iS, c in enumerate(S):\n",
    "                if c%i==0 or i%c==0:\n",
    "                    ret += put(i+1, S[:iS]+S[iS+1:])\n",
    "            return ret\n",
    "        return put(1, tuple(range(1,1+n)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countArrangement(self, n: int) -> int:\n",
    "        # 所有可选的数\n",
    "        start = tuple(i for i in range(1,n+1))\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(i, available):\n",
    "            # 到最后一个数了\n",
    "            if i == n:\n",
    "                # 最后一个位置需要是优美的\n",
    "                if available[0] % i == 0 or i % available[0] == 0:\n",
    "                    return 1\n",
    "                return 0\n",
    "            ans = 0\n",
    "            for num in available:\n",
    "                # 当前第i位也需要是优美的\n",
    "                if num % i == 0 or i % num == 0:\n",
    "                    # 去掉被使用的数\n",
    "                    tmp = list(available)\n",
    "                    tmp.remove(num)\n",
    "                    ans += dfs(i+1, tuple(tmp))\n",
    "            return ans\n",
    "        \n",
    "        return dfs(1, start)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countArrangement(self, n: int) -> int:\n",
    "        res = []\n",
    "        tmp = []\n",
    "        visited = set()\n",
    "\n",
    "        def dfs(level, cur):\n",
    "            if cur in visited:\n",
    "                return \n",
    "            if not (level % cur == 0 or cur % level == 0):\n",
    "                return \n",
    "            if level == n:\n",
    "                res.append(tmp.copy())\n",
    "                return\n",
    "            visited.add(cur)\n",
    "            tmp.append(cur)\n",
    "            for next in range(1,n+1):\n",
    "                dfs(level+1, next)\n",
    "            visited.remove(cur)\n",
    "            tmp.pop()\n",
    "   \n",
    "        for i in range(1,n+1):\n",
    "            dfs(1, i)\n",
    "        # print(res)\n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def countArrangement(self, n: int) -> int:\n",
    "        # 缓存数据加速算法\n",
    "        @lru_cache(maxsize=None, typed=False)\n",
    "\n",
    "        def countArrangementR(lis, idx):\n",
    "\n",
    "            if len(lis)==0:\n",
    "                return 1\n",
    "\n",
    "            ans=0\n",
    "\n",
    "            for i in range(len(lis)):\n",
    "\n",
    "                if(lis[i]%idx==0 or idx%lis[i]==0):\n",
    "\n",
    "                    ans+=countArrangementR(lis[:i]+lis[i+1:], idx+1)\n",
    "\n",
    "            return ans\n",
    "\n",
    "       \n",
    "\n",
    "        return countArrangementR(tuple(range(1, n + 1)),1)\n",
    "\n",
    "    \n",
    "\n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countArrangement(self, n: int) -> int:\n",
    "        memo = Counter()\n",
    "        def dfs(used, nums2use):\n",
    "            if used == n: return 1\n",
    "            if memo.get((used,tuple(nums2use)),0):\n",
    "                return memo[(used,tuple(nums2use))]\n",
    "            res = 0\n",
    "            for i in range(len(nums2use)):\n",
    "                if not nums2use[i] % (used+1) or not (used+1)% nums2use[i]:\n",
    "                    res += dfs(used+1,nums2use[:i]+nums2use[i+1:])\n",
    "            memo[(used,tuple(nums2use))] = res\n",
    "            return res\n",
    "        nums = [i for i in range(1,n+1)]\n",
    "        return dfs(0,nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countArrangement(self, n: int) -> int:\n",
    "        f=[[0]*n for _ in range(1<<n)]\n",
    "        #f[s][i] 已经使用的数字状态为s，最后一个数字是(i+1)\n",
    "        for i in range(n):\n",
    "            f[1<<i][i]=1\n",
    "        for s in range(1,1<<n):\n",
    "            idx=s.bit_count()+1\n",
    "            for i in range(n):\n",
    "                if s>>i&1:\n",
    "                    for j in range(n):\n",
    "                        if s>>j&1==0 and (idx%(j+1)==0 or (j+1)%idx==0):\n",
    "                            f[s|1<<j][j]+=f[s][i]\n",
    "        return sum(f[-1])\n",
    "\n",
    "                     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countArrangement(self, n: int) -> int:\n",
    "       \n",
    "        res=[]\n",
    "        path=[]\n",
    "        def backtrack(path):\n",
    "            if len(path)==n:\n",
    "                \n",
    "                res.append(path[:])\n",
    "                \n",
    "            for i in range(1,n+1):\n",
    "                if i in path:\n",
    "                    continue\n",
    "                if i%(len(path)+1)==0 or (len(path)+1)%i==0:\n",
    "                    path.append(i)\n",
    "                    backtrack(path)\n",
    "                    path.pop()\n",
    "        backtrack(path)\n",
    "        return len(res)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countArrangement(self, n: int) -> int:\n",
    "        # 全排列回溯\n",
    "        res = []\n",
    "        def pailie(li,tmp):\n",
    "            if not li:\n",
    "                res.append(tmp)\n",
    "                return\n",
    "            for i in range(len(li)):\n",
    "                if (len(tmp) + 1) % li[i] == 0 or li[i] % (len(tmp)+1) == 0:\n",
    "                    pailie(li[:i]+li[i+1:],tmp + [li[i]])\n",
    "        pailie(list(range(1,n+1)),[])\n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countArrangement(self, n: int) -> int:\n",
    "        res=[]\n",
    "        pre_res=[]\n",
    "        used=[0 for _ in range(n)]\n",
    "        arr=[i for i in range(1,n+1)]\n",
    "        def backtrack(used,pre_num):\n",
    "            if pre_res!=[]:\n",
    "                if pre_res[-1]%len(pre_res)!=0 and len(pre_res)%pre_res[-1]!=0:\n",
    "                    return\n",
    "            if len(pre_res)>=len(pre_num):\n",
    "                res.append(pre_res[:])\n",
    "                return\n",
    "            for i in range(len(arr)):\n",
    "                if used[i]==1:\n",
    "                    continue\n",
    "                pre_res.append(arr[i])\n",
    "                used[i]=1\n",
    "                backtrack(used,pre_num)\n",
    "                pre_res.pop()\n",
    "                used[i]=0\n",
    "        backtrack(used,arr)\n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countArrangement(self, n: int) -> int:\n",
    "        @lru_cache(None)\n",
    "        def recur(pos,rem):\n",
    "            if not rem:\n",
    "                return 1\n",
    "            res = 0\n",
    "            for i in range(len(rem)):\n",
    "                if rem[i]%pos == 0 or pos%rem[i] == 0:\n",
    "                    cp = list(rem)\n",
    "                    cp = tuple(cp[:i]+cp[i+1:])\n",
    "                    res += recur(pos+1,cp)\n",
    "            return res\n",
    "        return recur(1,tuple([i+1 for i in range(n)]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countArrangement(self, n: int) -> int:\n",
    "        nums = []\n",
    "        def demo(tmp):\n",
    "            length = len(tmp)\n",
    "            if length == n: \n",
    "                nums.append(tmp[::])\n",
    "                return \n",
    "            for j in range(1, n+1):\n",
    "                \n",
    "                if length == 0 or ((j not in tmp) and (j % (length+1) == 0 or (length+1) % j == 0 )):\n",
    "                    tmp.append(j)\n",
    "                    demo(tmp)\n",
    "                    tmp.pop()\n",
    "        \n",
    "        demo([])\n",
    "        return len(nums)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countArrangement(self, n: int) -> int:\n",
    "        self.res = []\n",
    "        \n",
    "\n",
    "        def match(a, b):\n",
    "            if a%b == 0 or b%a == 0:\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "\n",
    "        def backtrack(tmp):\n",
    "            if len(tmp) == n:\n",
    "                self.res.append(tmp[:])\n",
    "                return\n",
    "            \n",
    "            \n",
    "            for i in range(1, n+1):\n",
    "                if i not in tmp and match(len(tmp)+1, i):\n",
    "                    tmp.append(i)\n",
    "                    backtrack(tmp)\n",
    "                    tmp.pop()\n",
    "            \n",
    "\n",
    "        \n",
    "        backtrack([])\n",
    "\n",
    "        return len(self.res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countArrangement(self, n: int) -> int:\n",
    "        self.res=[]\n",
    "        helper=[i for i in range(1,n+1)]\n",
    "        def backtracking(tmp,used):\n",
    "            if len(tmp) == n:\n",
    "                self.res.append(tmp[:])\n",
    "                return\n",
    "            for i in range(len(helper)):\n",
    "                if used[i] == 0 and (helper[i]%(len(tmp)+1) == 0 or (len(tmp)+1)%helper[i] == 0):\n",
    "                    tmp.append(helper[i])\n",
    "                    used[i] = 1\n",
    "                    backtracking(tmp,used)\n",
    "                    used[i] = 0\n",
    "                    tmp.pop()\n",
    "        backtracking([],[0]*n)\n",
    "        return len(self.res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countArrangement(self, n: int) -> int:\n",
    "        res = 0\n",
    "        path = []\n",
    "        temp = []\n",
    "        visited = [False] * n\n",
    "        def dfs(n):\n",
    "            nonlocal res\n",
    "            if len(path) == n:\n",
    "                temp.append(path[:])\n",
    "                res += 1\n",
    "                return\n",
    "            for i in range(1, n+1):\n",
    "                if (len(path) + 1)%i == 0 or i%(len(path) + 1) == 0:\n",
    "                    if not visited[i-1]:\n",
    "                        visited[i-1] = True\n",
    "                        path.append(i)\n",
    "                        dfs(n)\n",
    "                        path.pop()\n",
    "                        visited[i-1] = False\n",
    "        dfs(n)\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def countArrangement(self, n: int) -> int:\n",
    "        def getPositions(x):\n",
    "            results=[]\n",
    "            for i in range(1,n+1):\n",
    "                if x//i==x/i or i//x==i/x:\n",
    "                    results.append(i)\n",
    "            return results\n",
    "        # 求每个数字可能的位置\n",
    "        m={}\n",
    "        for i in range(1,n+1):\n",
    "            m[i]=getPositions(i)\n",
    "\n",
    "        # 按位置到数字建立倒排索引,可以省略，因为和m一样\n",
    "        # reverse_m=defaultdict(list)\n",
    "        # for key,val in m.items():\n",
    "        #     for v in val:\n",
    "        #         reverse_m[v].append(key)\n",
    "        # print(reverse_m==m)\n",
    "        def dfs(pos,solution,results):\n",
    "            # return\n",
    "            if pos==n+1:\n",
    "                results.append(solution.copy())\n",
    "                return\n",
    "            \n",
    "            for val in m[pos]:\n",
    "                if val not in solution:\n",
    "                    solution.append(val)\n",
    "                    dfs(pos+1,solution,results)\n",
    "                    solution.pop()\n",
    "        solution=[]\n",
    "        results=[]\n",
    "        dfs(1,solution,results)\n",
    "        print(results)\n",
    "        return len(results)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "lists = []\n",
    "class Solution:\n",
    "\n",
    "    def countArrangement(self, n: int) -> int:\n",
    "\n",
    "    \n",
    "        def search(fo,nums,cnt):\n",
    "            for num in nums:\n",
    "                if num % cnt == 0 or cnt % num == 0:\n",
    "                    new_nums = nums[:]\n",
    "                    new_nums.remove(num)\n",
    "                    if cnt == 1:\n",
    "                        global lists\n",
    "                        lists.append(fo+[num])\n",
    "                        return\n",
    "                    search(fo+[num],new_nums,cnt-1)\n",
    "            return\n",
    "        cur = []\n",
    "        for i in range(n):\n",
    "            cur.append(i+1)\n",
    "        search([],cur,n)\n",
    "        global lists\n",
    "        #print(lists)\n",
    "        res = 0\n",
    "        for j in lists:\n",
    "            if len(j) == n:\n",
    "                res+=1\n",
    "        #lists = list(set(lists))\n",
    "        return res\n",
    "\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countArrangement(self, n: int) -> int:\n",
    "        # at each position we make a decision, just a simple backtrack promble\n",
    "        # a possible \n",
    "        if n < 3: return n\n",
    "\n",
    "        path = []\n",
    "        \n",
    "        def backtrack(rest_nums, cur_list):\n",
    "            if len(rest_nums) == 1:\n",
    "                last_one = list(rest_nums)[0]\n",
    "                if (len(cur_list) + 1) % last_one == 0 or last_one % (len(cur_list) + 1) == 0:\n",
    "                    path.append(cur_list + [last_one])\n",
    "                return\n",
    "\n",
    "            for num in rest_nums:\n",
    "                if (len(cur_list) + 1) % num == 0 or num % (len(cur_list) + 1) == 0:\n",
    "                    new_rest_nums = rest_nums.copy()\n",
    "                    new_rest_nums.remove(num)\n",
    "                    backtrack(new_rest_nums.copy(), cur_list + [num])\n",
    "            return \n",
    "\n",
    "\n",
    "        backtrack({i for i in range(1, n+1)}, [])\n",
    "\n",
    "        return len(path)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countArrangement(self, n: int) -> int:\n",
    "        res = [False] * n\n",
    "        ans = []\n",
    " \n",
    "        def dps(ltmp):\n",
    "            if ltmp[-1] % len(ltmp) != 0 and len(ltmp) % ltmp[-1] != 0:\n",
    "                return\n",
    "            if len(ltmp) == n:\n",
    "                ans.append(ltmp[:])\n",
    "            else:\n",
    "                for i in range(n):\n",
    "                    if res[i] == True:\n",
    "                        continue\n",
    "                    res[i] = True\n",
    "                    dps(ltmp + [i + 1])\n",
    "                    res[i] = False\n",
    "        dps([1])\n",
    "        return len(ans)\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
